package com.leetcode.algorithm.y22.m08.w4;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 662. 二叉树最大宽度
 * 
 * https://leetcode.cn/problems/maximum-width-of-binary-tree/
 * 
 * @author jie.deng
 *
 */
class Question0662Solution01 {

	public int widthOfBinaryTree(TreeNode root) {
		int maxWidth = 0;
		if (root == null) {
			return maxWidth;
		}
		Deque<TreeNode> queue = new ArrayDeque<>();
		Map<TreeNode, Integer> map = new HashMap<>();
		queue.offerLast(root);
		map.put(root, 0);
		while (!queue.isEmpty()) {
			int left = map.get(queue.peekFirst()).intValue();
			int right = map.get(queue.peekLast()).intValue();
			maxWidth = Math.max(right - left + 1, maxWidth);
			int len = queue.size();
			Map<TreeNode, Integer> tmpMap = new HashMap<>();
			for (int i = 0; i < len; i++) {
				TreeNode node = queue.pollFirst();
				int seq = map.get(node).intValue();
				if (node.left != null) {
					queue.offerLast(node.left);
					tmpMap.put(node.left, 2 * seq + 1);
				}
				if (node.right != null) {
					queue.offerLast(node.right);
					tmpMap.put(node.right, 2 * seq + 2);
				}
			}
			map.clear();
			map.putAll(tmpMap);
		}
		return maxWidth;
	}

}